\section{Ocena podobieństwa znajdowanych rozwiązań lokalnie optymalnych dla wybranych instancji}
W celu porównania podobieństwa rozwiązań zwracanych przez algorytmy optymalizacji lokalnej zaproponowano następującą miarę podobieństwa. Kolejne miasta w jednym z rozwiązań są po kolei sprawdzane z drugim rozwiązaniem. Jeżeli w jednym i drugim rozwiązaniu miasto następująco po aktualnie sprawdzanym mieście (uwzględniając połączenie miasta ostatniego z miastem pierwszym w rozwiązaniu) jest takie samo, inkrementowany jest licznik podobieństw. Na koniec, licznik podobieństw jest dzielony przez długość rozwiązania, przez co otrzymujemy znormalizowaną wartość z zakresu $<0-1>$.

Przedstawmy obecnie działanie zaproponowanej miary na przykładzie. Dane są dwie instancje - $3-1-2-4-0$ oraz $2-4-1-0-3$. Kolejne kroki algorytmu przedstawione są w poniższej tabeli.

\begin{tabular}{|l|l|l|}
		\hline
		Rozwiązanie 1 & Rozwiązanie 2 & Licznik podobieństw\\
		\hline
		& & 0 \\
		3-1 & 3-2 & 0 \\
		1-2 & 1-0 & 0 \\
		2-4 & 2-4 & 1 \\
		4-0 & 4-1 & 1 \\
		0-3 & 0-3 & 2\\
		\hline
\end{tabular}

\noindent Uzyskany licznik podobieństw należy jeszcze podzielić przez długość rozwiązania ($5$), przez co otrzymujemy współczynnik podobieństwa instancji wynoszący $0,4$.

Obecnie przedstawione zostaną wyniki porównania rozwiązań zwracanych dla algorytmu steepest i greedy. Przeprowadzono testy polegające na 10-krotnym uruchomieniu algorytmów z tego samego losowego punktu startowego dla dwóch instancji: flv33.atsp oraz ftv55.atsp. Następnie obliczono miary podobieństwa wyników zwróconych przez tak uruchomione algorytmy. Wyniki przedstawione zostały w tabelach \ref{tab:sim_33} i \ref{tab:sim_55}. W kolumnach ustawione są kolejne uruchomienia algorytmu steepest, natomiast w wierszach algorytmu greedy. Elementy na głównej przekątnej informują o tym jak podobne rozwiązania zwracają algorytmy gdy startują z tego samego punktu, czy trafiają w to samo optimum lokalne, natomiast wartości poza główną przekątną mogą mówić więcej o istnieniu małej liczby lub nawet tylko jednego optimum lokalnego - mimo startu z różnych miejsc algorytmy ''staczają się'' w to samo miejsce.

\begin{table}[h!]
	\centering
       \begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
        \hline
		& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
		\hline
		1 & \textbf{0.29} & 0.35 & 0.29 & 0.26 & 0.24 & 0.21 & 0.21 & 0.29 & 0.35 & 0.32 \\    
		2 & 0.44 & \textbf{0.38} & 0.32 & 0.18 & 0.41 & 0.18 & 0.12 & 0.35 & 0.44 & 0.35 \\    
		3 & 0.32 & 0.21 & \textbf{0.24} & 0.47 & 0.29 & 0.24 & 0.26 & 0.18 & 0.24 & 0.32 \\ 
		4 &	0.29 & 0.26 & 0.29 & \textbf{0.15} & 0.29 & 0.26 & 0.32 & 0.24 & 0.15 & 0.29 \\   
		5 & 0.26 & 0.12 & 0.15 & 0.12 & \textbf{0.18} & 0.29 & 0.26 & 0.15 & 0.21 & 0.21 \\   
		6 & 0.26 & 0.35 & 0.18 & 0.18 & 0.26 & \textbf{0.32} & 0.21 & 0.29 & 0.29 & 0.26 \\   
		7 & 0.29 & 0.47 & 0.38 & 0.32 & 0.38 & 0.12 & \textbf{0.24} & 0.44 & 0.35 & 0.41 \\   
		8 & 0.32 & 0.12 & 0.18 & 0.24 & 0.24 & 0.29 & 0.41 & \textbf{0.18} & 0.18 & 0.29 \\   
		9 & 0.09 & 0.21 & 0.24 & 0.15 & 0.29 & 0.24 & 0.21 & 0.21 & \textbf{0.26} & 0.21 \\   
		10 & 0.35 & 0.12 & 0.26 & 0.29 & 0.24 & 0.18 & 0.21 & 0.32 & 0.18 & \textbf{0.24} \\
		\hline
		\end{tabular}
		\caption{Podobieństwo zwracanych rozwiązań dla instancji ftv33.atsp. W kolumnach algorytm steepest, w wierszach algorytm greedy, wytłuszczone elementy to podobieństwo wyników zwracanych dla tego samego punktu startowego.}
		\label{tab:sim_33}
\end{table}

\begin{table}[h!]
       \centering
       \begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
        \hline
		& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
		\hline
		1 & \textbf{0.14} & 0.21 & 0.21 & 0.2 & 0.2 & 0.16 & 0.29 & 0.21 & 0.14 & 0.18 \\
		2 & 0.32 & \textbf{0.29} & 0.13 & 0.23 & 0.21 & 0.2 & 0.25 & 0.2 & 0.38 & 0.13 \\   
		3 & 0.32 & 0.16 & \textbf{0.25} & 0.16 & 0.13 & 0.18 & 0.29 & 0.32 & 0.16 & 0.25 \\   
		4 & 0.36 & 0.18 & 0.2 & \textbf{0.27} & 0.21 & 0.21 & 0.23 & 0.21 & 0.27 & 0.16 \\   
		5 & 0.41 & 0.23 & 0.25 & 0.25 & \textbf{0.36} & 0.16 & 0.36 & 0.2 & 0.23 & 0.16 \\   
		6 & 0.27 & 0.29 & 0.2 & 0.18 & 0.29 & \textbf{0.23} & 0.34 & 0.21 & 0.2 & 0.16 \\   
		7 & 0.29 & 0.23 & 0.13 & 0.3 & 0.2 & 0.2 & \textbf{0.29} & 0.25 & 0.14 & 0.29 \\   
		8 & 0.21 & 0.18 & 0.2 & 0.21 & 0.21 & 0.21 & 0.23 & \textbf{0.32} & 0.2 & 0.21 \\   
		9 & 0.34 & 0.25 & 0.23 & 0.25 & 0.2 & 0.21 & 0.27 & 0.2 & \textbf{0.29} & 0.25 \\   
		10 & 0.29 & 0.2 & 0.18 & 0.29 & 0.2 & 0.29 & 0.29 & 0.16 & 0.25 & \textbf{0.21} \\
		\hline
		\end{tabular}
		\caption{Podobieństwo zwracanych rozwiązań dla instancji ftv55.atsp. W kolumnach algorytm steepest, w wierszach algorytm greedy, wytłuszczone elementy to podobieństwo wyników zwracanych dla tego samego punktu startowego.}
		\label{tab:sim_55}
\end{table}

Analizując przedstawione tabele możemy dojść do wniosku, że obydwie instancje są zróżnicowane w równomierny sposób. Nawet startując z tych samych punktów algorytmy trafiają na optima lokalne w niewielkim stopniu do siebie podobne. Globalnie również musi istnieć wiele lokalnych ektremów, gdyż elementy poza główną przekątną nie osiągają wysokich wartości podobieństwa.